﻿//https://leetcode.cn/problems/merge-k-sorted-lists/description/
//我的方法一：由于单次寻找最小节点慢，时间超时
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int num = lists.size();
        unordered_map<int, ListNode*> pos;//<链表，链表当前位置>
        for (int i = 0; i < num; i++)pos[i] = lists[i];

        ListNode* newHead = new ListNode(INT_MAX);
        ListNode* prev = newHead, * min = newHead;
        int minList = 0;
        int flag = 1;
        while (flag)
        {
            flag = 0;
            int i = 0;
            //单次
            for (i = 0; i < num; i++)
            {
                ListNode* cur = pos[i];
                if (cur == nullptr) {
                    pos[i] = cur;
                    continue;
                }
                flag = 1;
                if (min->val > cur->val)
                {
                    min = cur;
                    minList = i;
                }
            }
            if (flag == 0)break;
            if (pos[minList]) pos[minList] = min->next;
            minList = 0;

            prev->next = min;
            prev = min;
            min = newHead;
        }

        return newHead->next;
    }
};
//我的方法二：利用multimap自带排序+不去重
/*Definition for singly - linked list.
* struct ListNode {
    *int val;
    *ListNode* next;
    *ListNode() : val(0), next(nullptr) {}
    *ListNode(int x) : val(x), next(nullptr) {}
    *ListNode(int x, ListNode* next) : val(x), next(next) {}
    *
};
*/
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*> tmplists = lists;
        multimap<int, ListNode*> total;//<val,ListNode>
        int flag = 1;
        while (flag)
        {
            flag = 0;
            for (int i = 0; i < tmplists.size(); i++)
            {

                ListNode* curNode = tmplists[i];
                if (curNode == nullptr)continue;
                total.insert(make_pair(curNode->val, curNode));
                flag = 1;
                tmplists[i] = curNode->next;
            }
        }
        ListNode* newHead = new ListNode;
        ListNode* cur = newHead;
        for (auto node : total)
        {
            cout << node.first << endl;
            cur->next = node.second;
            cur = cur->next;
        }

        return newHead->next;
    }
};
//答案
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution
{
	struct cmp
	{
		bool operator()(const ListNode* l1, const ListNode* l2)
		{
			return l1->val > l2->val;
		}
	};
public:
	ListNode* mergeKLists(vector<ListNode*>& lists)
	{
		// 创建⼀个⼩根堆
		priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
		// 让所有的头结点进⼊⼩根堆
		for (auto l : lists)
			if (l) heap.push(l);
		// 合并 k 个有序链表
		ListNode* ret = new ListNode(0);
		ListNode* prev = ret;
		while (!heap.empty())
		{
			ListNode* t = heap.top();
			heap.pop();
			prev->next = t;
			prev = t;
			if (t->next) heap.push(t->next);
		} prev = ret->next;
		delete ret;
		return prev;
	}
};